import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * Created With IntelliJ IDEA
 * Description:leetcode：155. 最小栈
 * <a href="https://leetcode.cn/problems/min-stack/">...</a>
 * User: DELL
 * Data: 2023-01-08
 * Time: 10:05
 */

//本题主要是学习维护最小栈的方法，这里我是模拟实现了一个栈，然后最小
//栈是用的JAVA自带的LinkedList，后续属于是写麻烦了，其实可以不用
//自己写栈来维护，可以均使用系统的数据结构
class MinStack {
    public static int DEFAULT_SIZE = 100;

    private int[] element;
    private int size;
    private final Deque<Integer> minStack; //最小栈
    private int capacity;

    public MinStack() {
        this.element = new int[DEFAULT_SIZE];
        this.minStack = new LinkedList<>();
        //最小栈中压入最大整数，方便后续进行比较
        this.minStack.push(Integer.MAX_VALUE);
        this.capacity = DEFAULT_SIZE;
    }

    public void push(int val) {
        //检查是否需要扩容
        ensureCapacity();
        //压入数据
        element[size++] = val;
        //维护最小栈
        this.minStack.push(Math.min(minStack.peek(),val));
    }

    private void ensureCapacity () {
        if (this.size >= capacity) {
            //二倍扩容
            this.element = Arrays.copyOf(element,2*capacity);
            this.capacity *= 2;
        }
    }

    public void pop() {
        if (this.size <= 0) {
            return;
        }
        //这里切记是--size，不可以写成size--，否则会导致越界
        element[--size] = 0;
        minStack.pop();
    }

    public int top() {
        //题目中要求pop、top 和 getMin 操作总是在非空栈上调用
        //否则这里需要检验，是空栈后抛出异常
        return element[size - 1];
    }

    public int getMin() {
        //题目中要求pop、top 和 getMin 操作总是在非空栈上调用
        //否则这里需要检验，不合法后抛出异常
        return this.minStack.peek();
    }
}